Search for: All records

Abstract We investigate the validity of the “Einstein relations” in the general setting of unimodular random networks. These are equalities relating scaling exponents:$$\begin{aligned} d_{w} &= d_{f} + \tilde{\zeta }, \\ d_{s} &= 2 d_{f}/d_{w}, \end{aligned}$$whered_wis the walk dimension,d_fis the fractal dimension,d_sis the spectral dimension, and$$\tilde{\zeta }$$is the resistance exponent. Roughly speaking, this relates the mean displacement and return probability of a random walker to the density and conductivity of the underlying medium. We show that ifd_fand$$\tilde{\zeta } \geqslant 0$$exist, thend_wandd_sexist, and the aforementioned equalities hold. Moreover, our primary new estimate$$d_{w} \geqslant d_{f} + \tilde{\zeta }$$is established for all$$\tilde{\zeta } \in \mathbb{R}$$. For the uniform infinite planar triangulation (UIPT), this yields the consequenced_w=4 usingd_f=4 (Angel in Geom. Funct. Anal. 13(5):935–974, 2003) and$$\tilde{\zeta }=0$$(established here as a consequence of the Liouville Quantum Gravity theory, following Gwynne-Miller 2020 and (Ding and Gwynne in Commun. Math. Phys. 374(3):1877–1934, 2020)). The conclusiond_w=4 had been previously established by Gwynne and Hutchcroft (2018) using more elaborate methods. A new consequence is thatd_w=d_ffor the uniform infinite Schnyder-wood decorated triangulation, implying that the simple random walk is subdiffusive, sinced_f>2. 

We present an O((log n)²)-competitive algorithm for metrical task systems (MTS) on any n-point metric space that is also 1-competitive for service costs. This matches the competitive ratio achieved by Bubeck, Cohen, Lee, and Lee (2019) and the refined competitive ratios obtained by Coester and Lee (2019). Those algorithms work by first randomly embedding the metric space into an ultrametric and then solving MTS there. In contrast, our algorithm is cast as regularized gradient descent where the regularizer is a multiscale metric entropy defined directly on the metric space. This answers an open question of Bubeck (Highlights of Algorithms, 2019).